The invention relates to a method and arrangement for storing data items in a memory, comprising the steps of dividing each data item into successive data pieces of decreasing significance, and storing said successive data pieces in respective successive layers of said memory. The invention also relates to a method and arrangement for reading said data items thus stored.
A method as defined in the opening paragraph is generally known. For example, bit map images are usually stored in pixel memories which are divided into as many layers or planes as there are bits per pixel, each layer storing the bits of a particular significance.
To save memory costs, information is often subjected to lossy compression prior to storage. Various compression algorithms are known and some of them have meanwhile been standardized for commercial applications. For example, JPEG is an image compression standard, MPEG and H.263 are video compression standards. Images are divided into blocks and subjected to an orthogonal transform such as the discrete cosine transform (DCT). The coefficients of each DCT block are quantized and entropy-encoded. A buffer control circuit regulates the quantization in such a way that a desired channel bit rate is obtained and/or the image (or a sequence of images) can be stored in a memory of a given capacity, for example, an optical disk.
Predictive encoders such as MPEG encoders have one or more frame memories for temporal storage of prediction frames. Usually, the prediction frames are stored uncompressed in pixel memories but there is a trend towards locally compressing and decompressing the prediction images so that the frame memories can be cost-effectively embedded on the same silicon as the encoder itself. An example of such an encoder is disclosed in Applicant""s co-pending International Patent Application IB99/00151 (PHN 16.769).
There are thus various reasons to compress information so that it fits in a given fixed size memory. Sophisticated image compression algorithms achieve this by pre-analyzing each image and distributing the quantization errors evenly. However, this requires additional memory, which is exactly what is to be avoided.
It is an object of the invention to provide an attractive alternative method of storing data items in a memory.
The method in accordance with the invention employs a memory which has a decreasing number of memory locations in its successive memory layers. When a data piece is applied to a candidate memory location in which a data piece has previously been stored, the perceptual relevance of at least said stored data piece is compared with the perceptual relevance of at least said applied data piece in accordance with a predetermined criterion. If the perceptual relevance of the stored data piece is larger, the applied data piece is not stored in said candidate memory location. If the perceptual relevance of the applied data piece is larger, the stored data piece in the candidate memory location is replaced by the applied data piece, and link data is stored in the memory to link said candidate memory location to the parent memory location in which the higher significant data piece of the same data item is stored.
It is achieved with the invention that, each time a data item is fetched to the chain of memory layers, its data pieces will have to compete with previously stored pieces. As only the xe2x80x9cwinnersxe2x80x9d are stored in the memory, the information is automatically compressed and all memory resources are eventually used for storing the perceptually most relevant data pieces. The information is thus automatically compressed to such an extent that it precisely fits in the memory. A bit rate control mechanism and pre-analysis of the information can be dispensed with.
A particular useful application of the invention is compressed storage of prediction images in an embedded memory of hybrid encoders. Each image is divided into blocks and subjected to the discrete cosine transform (DCT). The DCT blocks of the image constitute the data items. They are hierarchically quantized to obtain the data pieces of decreasing significance.
These and further aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter.